package cn.aylog.algorithm;

import java.util.Arrays;

/**
 * 归并排序
 */
public class MergeSort {
    public static void main(String[] args) {
        // int[] arr = {8, 9, 1, 7, 2, 3, 5, 4, 6};
        int len = 80000;
        int[] arr = new int[len];
        for(int i=0; i<len; i++) arr[i] = (int)(Math.random()*8000000);
        int[] temp = new int[arr.length];
        long start = System.currentTimeMillis();
        mergeSort(arr, 0, arr.length - 1, temp);
        long end = System.currentTimeMillis();
        System.out.println("排序耗时: " + (end - start));
        // System.out.println(Arrays.toString(arr));
    }

    public static void mergeSort(int[] arr, int left, int right, int[] temp) {
        if(left < right) {
            int mid = (left+right) / 2;
            mergeSort(arr, left, mid, temp);
            mergeSort(arr, mid+1, right, temp);
            merge(arr, left, mid, right, temp);
        }
    }

    /**
     * 数组合并
     * @param arr 待合并的数组
     * @param left 数组起始下标
     * @param mid 数组分隔位置
     * @param right 数组起始下标
     * @param temp 中间数组
     */
    public static void merge(int[] arr, int left, int mid, int right, int[] temp) {
        int x = left, y = mid + 1, t = left;
        // 将两个数组按照从小到大的顺序合并到中间数组
        while (x <= mid && y <= right) {
            if (arr[x] < arr[y]) {
                temp[t++] = arr[x++];
            } else {
                temp[t++] = arr[y++];
            }
        }
        // 将剩余数据合并到中间数组
        while (x <= mid) temp[t++] = arr[x++];
        while (y <= right) temp[t++] = arr[y++];
        // 将中间数组的数据复制到arr上
        for (int i = left; i <= right; i++) arr[i] = temp[i];
    }
}
